package com.scheuk.puzzles;

import java.util.BitSet;  

public class Primes  
{  
	
	public static void getPrimes(long maxNum) 
	{
				  
        if( maxNum > Integer.MAX_VALUE )  
        {  
            System.err.println( "TOO BIG - maximum must be less than or equal to " + Integer.MAX_VALUE );  
            System.exit( 1 );  
        }  
  
        int             max = (int)maxNum;  
        int             sqrt = (int)Math.sqrt( max );  
        BitSet          bitSet = new BitSet( max + 1 );
        int[]			primeSet;
        int             i, j;  
        long            start, stop;  
  
        start = System.currentTimeMillis();  
  
        //+++++ the meat and potatoes +++++  
  
        i = 2;  
        for( j=i*2 ; j <= max ; j+=i )  
            bitSet.set( j );  
  
        for( i=3 ; i <= sqrt ; i+=2 )  
            if( ! bitSet.get(i) )  
                for( j=i*2 ; j <= max ; j+=i )  
                    bitSet.set( j );  
  
        //+++++++++++++++++++++++++++++++++  
  
        stop = System.currentTimeMillis();  
  
        System.out.format( "N=%,d sec=%.2f\n", max, ((stop - start)/1000.0) );  
  
        for( i=2 ; i < max ; i++ )  
            if( ! bitSet.get(i) )  
                System.out.format( "%d ", i );  
        		
	}
	
    public static void main( String[] args )  
    {  
    	Primes.getPrimes(2520);
    }
} 
